package com.fjl.list.leetcode23;

import com.fjl.list.ListNode;

import java.util.PriorityQueue;

/**
 * @Description
 * @Author: 01195
 * @Date: 2025/2/12 15:53
 */
public class MergeKSingleLinkedList {
    public static void main(String[] args) {

    }

    /*
        给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
     */
    public ListNode mergeKLists(ListNode[] lists){
        /*
        合并 k 个有序链表的逻辑类似合并两个有序链表，难点在于，如何快速得到 k 个节点中的最小节点，接到结果链表上？
        因为这里是K个，数量不确定，所以不能和合并两个有序链表一样去while循环
        这里我们就要用到优先级队列这种数据结构，把链表节点放入一个最小堆，就可以每次获得 k 个节点中的最小节点。
         */
        if (lists.length == 0) return null;
        // 创建虚拟头节点
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        // 优先级队列, 最小堆
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(
                lists.length, (a, b) -> (a.val - b.val)
        );
        // 将 k 个链表的头结点加入最小堆
        for (ListNode head : lists) {
            if (head != null) {
                priorityQueue.add(head);
            }
        }
        while (!priorityQueue.isEmpty()) {
            ListNode node = priorityQueue.poll();
            cur.next = node;
            if (node.next != null) {
                priorityQueue.add(node.next);
            }
            // cur 指针不断前进
            cur = cur.next;
        }

        return dummy.next;
    }
}
